#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> dp(len, vector<int>(len, 2));
        unordered_map<int, int> hash;
        hash[nums[0]] = 0; hash[nums[1]] = 1;
        for (int j = 2; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (hash.count(2 * nums[i] - nums[j])) {
                    int k = hash[2 * nums[i] - nums[j]];
                    if (k < i) {
                        dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                    }
                }
            }
            hash[nums[j]] = j;
        }
        int ans = 0;
        for (auto& e : dp) {
            for (auto& d : e) {
                ans = max(d, ans);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> dp(len, vector<int>(len, 2));
        for (int j = 2; j < len; j++) {
            for (int i = 0; i < j; i++) {
                for (int k = 0; k < i; k++) {
                    if (2 * nums[i] == nums[k] + nums[j]) {
                        dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                    }
                }
            }
        }
        int ans = 0;
        for (auto& e : dp) {
            for (auto& d : e) {
                ans = max(d, ans);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> dp(len, vector<int>(len, 2));
        unordered_map<int, vector<int>> hash;
        hash[nums[0]].push_back(0);
        hash[nums[1]].push_back(1);
        int ans = 2;
        for (int j = 2; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (hash.count(2 * nums[i] - nums[j])) {
                    for (auto& e : hash[2 * nums[i] - nums[j]]) {
                        int k = e;
                        if (k < i) {
                            dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                        }
                    }
                }
                ans = max(ans, dp[i][j]);
            }
            hash[nums[j]].push_back(j);
        }
        return ans;
    }
};

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> dp(len, vector<int>(len, 2));
        unordered_map<int, int> hash;
        // hash[nums[0]] = 0; hash[nums[1]] = 1;
        int ans = 2;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (hash.count(2 * nums[i] - nums[j])) {
                    int k = hash[2 * nums[i] - nums[j]];
                    if (k < i) {
                        dp[i][j] = max(dp[i][j], dp[k][i] + 1);
                    }
                    ans = max(ans, dp[i][j]);
                }
            }
            hash[nums[i]] = i;
        }
        return ans;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int len = nums.size();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        unordered_map<long long, vector<int>> hash;
        hash[nums[0]].push_back(0);
        if (len > 1)hash[nums[1]].push_back(1);
        for (int j = 2; j < len; j++) {
            for (int i = 1; i < j; i++) {
                long long digit = 2 * (long long)nums[i] - nums[j];
                if (hash.count(digit)) {
                    for (auto& e : hash[digit]) {
                        int k = e;
                        if (k < i) {
                            dp[i][j] += dp[k][i] + 1;
                        }
                    }
                }
            }
            hash[nums[j]].push_back(j);
        }
        int ans = 0;
        for (auto& e : dp) {
            for (auto& d : e) {
                ans += d;
            }
        }
        return ans;
    }
};

